/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package agenda;

/**
 *
 * @author ebert
 */
import java.util.LinkedList;
import java.util.Queue;
import javax.swing.*;

class Btree<clase>{
	Bnodo p=new Bnodo();
	Bnodo Xder = new Bnodo();
	Bnodo Xizq = new Bnodo();
	NodoPr X;
	Bnodo Xr;
	String salida="",imps="";
	boolean EmpA = false,Esta=false;



        void Inserta(int clave,clase ob){
            NodoPr<clase> fa=new NodoPr <clase>(clave,ob);
		Insertaa(fa,p);
	}
	//auxiliar de inserta nodo
	public void Insertaa(NodoPr clave, Bnodo raiz){
		Empujar(clave,raiz);
		if(EmpA){
			p=new Bnodo();
			p.Cuentas= 1;
			p.Claves[0]=X;
			p.Ramas[0]=raiz;
			p.Ramas[1]=Xr;
		}
		//JOptionPane.showMessageDialog(null,"Insercion Completa");
	}
	//Empuja los elementos del arbol
	public void Empujar(NodoPr clave, Bnodo raiz){
		int k=0;
		Esta=false;
		if(Vacio(raiz)){
			EmpA=true;
			X=clave;
			Xr=null;
		}
		else{
			k=BuscarNodo(clave, raiz);
			if(Esta){
				JOptionPane.showMessageDialog(null,"No hay claves repetidas");
				EmpA=false;
			}
			else{
				Empujar(clave, raiz.Ramas[k]);
				if(EmpA){
					if(raiz.Cuentas < 4){
						EmpA = false;
						MeterHoja(X, raiz, k);
					}
					else{
						EmpA = true;
						DividirN(X, raiz, k);
					}
				}
		    }
		}
	}
	//Meter hoja


	public void MeterHoja(NodoPr clave, Bnodo raiz, int k){
		int i = raiz.Cuentas;
		while (i != k){
			raiz.Claves[i] = raiz.Claves[i-1];
			raiz.Ramas[i+1] = raiz.Ramas[i];
			--i;
		}
		raiz.Claves[k] = clave;
		raiz.Ramas[k+1] = Xr;
		raiz.Cuentas = ++raiz.Cuentas;
	}

	//Dividir nodo
	public void DividirN(NodoPr Clave, Bnodo Raiz, int k){
		int pos=0;
		int Posmda=0;
		if (k <= 2)
			Posmda = 2;
		else{
			Posmda = 3;
		}
		Bnodo Mder = new Bnodo();
		pos = Posmda+1;
		while (pos != 5){
			 Mder.Claves [(pos - Posmda)-1] = Raiz.Claves[pos-1];
			 Mder.Ramas [pos - Posmda] = Raiz.Ramas[pos];
			 ++pos;
		}
		Mder.Cuentas = 4 - Posmda;
		Raiz.Cuentas = Posmda;
		if (k <= 2)
			MeterHoja(Clave, Raiz, k);
		else{
			MeterHoja(Clave, Mder, (k - Posmda));
		}
		X = Raiz.Claves[Raiz.Cuentas-1];
		Mder.Ramas[0] = Raiz.Ramas[Raiz.Cuentas];
		Raiz.Cuentas = --Raiz.Cuentas;
		Xr=Mder;
	}

	void Eliminar(NodoPr clave){
		if(Vacio(p)){
			JOptionPane.showMessageDialog(null,"No hay elementos");
		}
		else
			Eliminara(p,clave);
	}

	public void Eliminara(Bnodo Raiz, NodoPr clave){
		try{
			EliminarRegistro(Raiz, clave);
		}
		catch(Exception e){
			Esta=false;
                        System.out.println("maldito error");
		}
		if (!Esta)
			JOptionPane.showMessageDialog(null,"No se encontro el elemento");
		else{
			if (Raiz.Cuentas == 0)
                        Raiz = Raiz.Ramas[0];
			p=Raiz;
			JOptionPane.showMessageDialog(null,"Eliminacion completa");
		}
	}
	//Elimina el registro

	public void EliminarRegistro(Bnodo raiz, NodoPr c){
		int pos = 0;
		NodoPr sucesor;
		if (Vacio(raiz))
			Esta = false;
		else{
			pos = BuscarNodo(c, raiz);
			if (Esta){
				if (Vacio(raiz.Ramas[pos-1]))
					Quitar(raiz, pos);
				else{
					Sucesor(raiz, pos);
					EliminarRegistro (raiz.Ramas[pos], raiz.Claves[pos-1]);
				}
			}
			else{
				EliminarRegistro(raiz.Ramas[pos], c);
				if ((raiz.Ramas[pos] != null) && (raiz.Ramas[pos].Cuentas < 2))
					Restablecer(raiz, pos);
			}
		}
	}
	//Busca el sucesor
	public void Sucesor (Bnodo raiz, int k){
		Bnodo q=raiz.Ramas[k];
		while(!Vacio(q.Ramas[0]))
			q=q.Ramas[0];
		raiz.Claves[k-1]=q.Claves[0];
	}
	//Combina para formar un nodo
	public void Combina(Bnodo raiz, int pos){
		int j;
		Xder = raiz.Ramas[pos];
		Xizq = raiz.Ramas[pos-1];
		Xizq.Cuentas++;
		Xizq.Claves[Xizq.Cuentas-1] = raiz.Claves[pos-1];
		Xizq.Ramas[Xizq.Cuentas] = Xder.Ramas[0];
		j = 1;
		while (j != Xder.Cuentas+1){
			Xizq.Cuentas++;
			Xizq.Claves[Xizq.Cuentas-1] = Xder.Claves[j-1];
			Xizq.Ramas[Xizq.Cuentas] = Xder.Ramas[j];
			j++;
		}
		Quitar(raiz, pos);
	}
	//Mueve a la derecha
	public void MoverDer(Bnodo raiz, int pos){
		int i = raiz.Ramas[pos].Cuentas;
		while (i != 0){
			raiz.Ramas[pos].Claves[i] = raiz.Ramas[pos].Claves[i-1];
			raiz.Ramas[pos].Ramas[i+1] = raiz.Ramas[pos].Ramas[i];
			--i;
		}
		raiz.Ramas[pos].Cuentas++;
		raiz.Ramas[pos].Ramas[1] = raiz.Ramas[pos].Ramas[0];
		raiz.Ramas[pos].Claves[0] = raiz.Claves[pos-1];
		raiz.Claves[pos-1] = raiz.Ramas[pos-1].Claves[raiz.Ramas[pos-1].Cuentas-1];
		raiz.Ramas[pos].Ramas[0] = raiz.Ramas[pos-1].Ramas[raiz.Ramas[pos-1].Cuentas];
		raiz.Ramas[pos-1].Cuentas--;
	}
	//Mover a la izquierda
	public void MoverIzq(Bnodo raiz, int pos){
		int i;
		raiz.Ramas[pos-1].Cuentas++;
		raiz.Ramas[pos-1].Claves[raiz.Ramas[pos-1].Cuentas-1] = raiz.Claves[pos-1];
		raiz.Ramas[pos-1].Ramas[raiz.Ramas[pos-1].Cuentas] = raiz.Ramas[pos].Ramas[0];
		raiz.Claves[pos-1] = raiz.Ramas[pos].Claves[0];
		raiz.Ramas[pos].Ramas[0] = raiz.Ramas[pos].Ramas[1];
		raiz.Ramas[pos].Cuentas--;
		i = 1;
		while (i != raiz.Ramas[pos].Cuentas+1){
			raiz.Ramas[pos].Claves[i-1] = raiz.Ramas[pos].Claves[i];
			raiz.Ramas[pos].Ramas[i] = raiz.Ramas[pos].Ramas[i+1];
			i++;
		}
	}
	//Quita el elemento
	public void Quitar (Bnodo raiz, int pos){
		int j = pos + 1;
		while (j != raiz.Cuentas+1){
			raiz.Claves [j-2] = raiz.Claves[j-1];
			raiz.Ramas [j-1] = raiz.Ramas[j];
			j++;
		}
		raiz.Cuentas--;
	}
	//Restablece el nodo
	public void Restablecer(Bnodo raiz, int pos){
		if (pos>0){
			if (raiz.Ramas[pos-1].Cuentas > 2)
				MoverDer(raiz, pos);
			else
				Combina(raiz, pos);
		}
		else{
			if (raiz.Ramas[1].Cuentas > 2)
				MoverIzq(raiz, 1);
			else
				Combina(raiz, 1);
		}
	}
	//Retorna true si el arbol esta vacio
	public boolean Vacio(Bnodo raiz){
		return (raiz==null || raiz.Cuentas==0);
	}
	//Buscar retorna true si lo encuentra y la posicion
	public int BuscarNodo(NodoPr clave, Bnodo raiz){
		int j=0;
		if(clave.nump < raiz.Claves[0].nump){
			Esta = false;
			j=0;
		}
		else{
			j = raiz.Cuentas;
			while (clave.nump < raiz.Claves[j-1].nump && j>1)
				--j;
			Esta = (clave.nump == raiz.Claves[j-1].nump);
		}
		return j;
	}


        String Grafico;



String inicio=" digraph demo { node [shape=\"record\"] edge[tailclip=\"false\"]";
	public void recorrer() {

		mostrar(p);
    Grafico+="}";
	}
String padre="";


public void mostrar(Bnodo raiz) {
		if (raiz != null) {
			if (raiz.Cuentas > 0) {

                    for(int d=0;d<raiz.Claves.length;d++){
                        try{
                           // System.out.println("este es el padre :"+raiz.nodosInternos[d].clave+"ademas el contedo del for es "+d);
                        }
                        catch(Exception s){
                        }
                    }
				//mostrar(raiz.hijos[k], k);
				//System.out.println("padre "+raiz.nodosInternos[0].getClave());

                                for (int i = 0; i < 5; i++) {
                                mostrar(raiz.Ramas[i]);
				}
				recorrerPagina(raiz);
				System.out.println("%%%%%");
			}else{

                        }
		}
	}
public String hha() {
    Grafico=inicio;
String law = "";
Queue<Bnodo> ss = new LinkedList<Bnodo>();
Queue<Integer> enteros = new LinkedList<Integer>();
ss.add(p);
enteros.add(0);
return Grafico+intento(ss, enteros, 1)+"}";
}
public String intento(Queue<Bnodo>ss, Queue<Integer> enter, int ultimo) {
Bnodo te = ss.poll();
String yas = "";
if (te != null) {
yas =recorrerPaginaDot(te, enter.poll(), ultimo);
Boolean n=true;
int y = 0;
while(n) {
if (y < 5) {
if (te.Ramas[y]!= null) {
ss.add(te.Ramas[y]);
enter.add(ultimo+y);
y++;
} else
n = false;
} else
n = false;
}
yas = yas + intento(ss,enter, ultimo+y);
//contador++;
}
return yas;
}

public String recorrerPaginaDot(Bnodo raiz, int contador, int serie) {
String avan = "";
if ((raiz != null) && (raiz.Cuentas > 0)) {
String h="";
String ramas="";
int i = 0;
int padree = contador;
Boolean continuar = true;
while(continuar) {
if (i < 4) {
if (raiz.Claves[i]!= null) {
//System.out.println(raiz.nodosInternos[i].getClave() + " " + raiz.nodosInternos[i].toString());
h = h + raiz.Claves[i].nump+ "|";
i++;
} else
continuar = false;
} else
continuar = false;
}
Boolean conti = true;
int hijo = contador+1;
String enlaces="";
int j = 0;
while(conti) {
if (j < 5) {
if (raiz.Ramas[j]!= null) {
//System.out.println(raiz.nodosInternos[i].getClave() + " " + raiz.nodosInternos[i].toString());
ramas = ramas + "<C" + padree + "" + j + ">|";
enlaces = enlaces + "P"+padree+":"+"C"+ padree + "" + j + "->" + "P"+ (serie+j) + "\n";
j++;
} else
conti = false;
} else
conti = false;
}
h = h.substring(0, h.length()-1);
if (ramas.length()>0)
ramas = ramas.substring(0, ramas.length()-1);
//h = h + "}";
avan = "P" + padree + "[label=\"{{" + h + "}" + "|{" + ramas + "}}\"]\n";
avan = avan + enlaces;
}
return avan;
}



static public LinkedList<Object> datos=new LinkedList<Object>();
private void recorrerPagina(Bnodo raiz) {
		int i = 0;
		Boolean continuar = true;

		while(continuar) {
			if (i < 4) {

		if (raiz.Claves[i]!= null) {

                         datos.add(raiz.Claves[i].contenido) ;

                                        i++;

				} else
					continuar = false;
			} else
				continuar = false;

		}
        }


}